{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Robots Within Budget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #binary-search #prefix-sum #sliding-window #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #二分查找 #前缀和 #滑动窗口 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumRobots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #预算内的最多机器人数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有&nbsp;<code>n</code>&nbsp;个机器人，给你两个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>chargeTimes</code> 和&nbsp;<code>runningCosts</code>&nbsp;，两者长度都为&nbsp;<code>n</code>&nbsp;。第&nbsp;<code>i</code>&nbsp;个机器人充电时间为&nbsp;<code>chargeTimes[i]</code>&nbsp;单位时间，花费&nbsp;<code>runningCosts[i]</code>&nbsp;单位时间运行。再给你一个整数&nbsp;<code>budget</code>&nbsp;。</p>\n",
    "\n",
    "<p>运行&nbsp;<code>k</code>&nbsp;个机器人 <strong>总开销</strong>&nbsp;是&nbsp;<code>max(chargeTimes) + k * sum(runningCosts)</code>&nbsp;，其中&nbsp;<code>max(chargeTimes)</code>&nbsp;是这&nbsp;<code>k</code>&nbsp;个机器人中最大充电时间，<code>sum(runningCosts)</code>&nbsp;是这 <code>k</code>&nbsp;个机器人的运行时间之和。</p>\n",
    "\n",
    "<p>请你返回在 <strong>不超过</strong>&nbsp;<code>budget</code>&nbsp;的前提下，你 <strong>最多</strong>&nbsp;可以 <strong>连续</strong>&nbsp;运行的机器人数目为多少。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>\n",
    "可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。\n",
    "选择前 3 个机器人，可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ，小于 25 。\n",
    "可以看出无法在 budget 以内连续运行超过 3 个机器人，所以我们返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>即使运行任何一个单个机器人，还是会超出 budget，所以我们返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>chargeTimes.length == runningCosts.length == n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= chargeTimes[i], runningCosts[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= budget &lt;= 10<sup>15</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-robots-within-budget](https://leetcode.cn/problems/maximum-number-of-robots-within-budget/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-robots-within-budget](https://leetcode.cn/problems/maximum-number-of-robots-within-budget/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,6,1,3,4]\\n[2,1,3,4,5]\\n25', '[11,12,19]\\n[10,8,7]\\n19']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        \n",
    "        n = len(chargeTimes)\n",
    "        def bs(size):\n",
    "            \n",
    "            t = []\n",
    "            c = 0\n",
    "            l = 0\n",
    "            for r in range(n):\n",
    "                heappush(t, (-chargeTimes[r], r))\n",
    "                c += runningCosts[r]\n",
    "                if r - l + 1 > size:\n",
    "                    c -= runningCosts[l]\n",
    "                    l += 1\n",
    "                    while t and t[0][1] < l:\n",
    "                        heappop(t)\n",
    "                if r - l + 1 == size:\n",
    "                    tmp = -t[0][0] + size * c\n",
    "                    if tmp <= budget: return True\n",
    "            return False\n",
    "        \n",
    "        l, h = 0, n\n",
    "        while l < h:\n",
    "            mid = l + (h - l + 1) // 2\n",
    "            if bs(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                h = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        n=len(chargeTimes)\n",
    "\n",
    "        res=0\n",
    "        q=deque()\n",
    "        i,j=0,0\n",
    "        bud=0\n",
    "        flag=0\n",
    "        while j<n:\n",
    "            bud+=runningCosts[j]\n",
    "            while q and q[-1]<chargeTimes[j]:\n",
    "                q.pop()\n",
    "            q.append(chargeTimes[j])\n",
    "            j+=1\n",
    "        \n",
    "            while q and (j-i)*bud+q[0]>budget:\n",
    "                bud-=runningCosts[i]\n",
    "                if q[0]==chargeTimes[i]:\n",
    "                    q.popleft()\n",
    "                i+=1\n",
    "            \n",
    "            res=max(res,j-i)\n",
    "        \n",
    "        return res\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        # 选一个子数组 ->  保证 max(chargeTimes) + k * sum(runningCosts) <= budget\n",
    "        # 滑动窗口 + 单调栈\n",
    "\n",
    "        # total 记录的是滑动窗口[left, right]内的和\n",
    "        ans, left, total, queue = 0, 0, 0, deque()\n",
    "        for right, (chargeTime, runningCost) in enumerate(zip(chargeTimes, runningCosts)):\n",
    "            # 处理窗口右侧：往里面队列里面加(索引)\n",
    "            while queue and chargeTimes[right] >= chargeTimes[queue[0]]:\n",
    "                queue.popleft()\n",
    "            queue.appendleft(right)\n",
    "            total += runningCost\n",
    "\n",
    "            # 处理窗口左侧:如果最大值已经超过budget\n",
    "            while queue and chargeTimes[queue[-1]] + (right - left + 1) * total > budget:\n",
    "                if queue[-1] == left:\n",
    "                    queue.pop()\n",
    "                total -= runningCosts[left]\n",
    "                left += 1\n",
    "            \n",
    "            ans = max(ans, right - left + 1)\n",
    "        \n",
    "        return ans \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        ans = s = left = 0\n",
    "        q = deque()\n",
    "        # 枚举区间右端点 right，计算区间左端点 left 的最小值\n",
    "        for right, (t, c) in enumerate(zip(chargeTimes, runningCosts)):\n",
    "            # 及时清除队列中的无用数据，保证队列的单调性\n",
    "            while q and t >= chargeTimes[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(right)\n",
    "            s += c\n",
    "            # 如果左端点 left 不满足要求，就不断右移 left\n",
    "            while q and chargeTimes[q[0]] + (right - left + 1) * s > budget:\n",
    "                # 及时清除队列中的无用数据，保证队列的单调性\n",
    "                if q[0] == left:\n",
    "                    q.popleft()\n",
    "                s -= runningCosts[left]\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        ans = sum_cost = left = 0\n",
    "        q = deque()\n",
    "        for right, (t, c) in enumerate(zip(chargeTimes, runningCosts)):\n",
    "            # 维护右端点\n",
    "            sum_cost += c\n",
    "            while q and t > q[-1]:\n",
    "                q.pop()\n",
    "            q.append(t)\n",
    "\n",
    "            # 维护左端点\n",
    "            while q and q[0] + sum_cost * (right - left + 1) > budget:\n",
    "                if q[0] == chargeTimes[left]:\n",
    "                    q.popleft()\n",
    "                sum_cost -= runningCosts[left]\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        h = []\n",
    "        n = len(chargeTimes)\n",
    "        res = 0\n",
    "        i, j = 0, 0\n",
    "        s = 0\n",
    "        while j < n:\n",
    "            ct = chargeTimes[j]\n",
    "            rc = runningCosts[j]\n",
    "            while h and h[-1] < ct:\n",
    "                h.pop()\n",
    "            \n",
    "            h.append(ct)\n",
    "            s += rc\n",
    "            \n",
    "            while h and h[0] + (j - i + 1) * s > budget:\n",
    "                if chargeTimes[i] == h[0]:\n",
    "                    h.pop(0)\n",
    "                s -= runningCosts[i]\n",
    "                i += 1\n",
    "            # print(i, j, h, s)\n",
    "            res = max(res, j - i + 1)\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        sl, s = SortedList(), 0\n",
    "        res, i = 0, 0\n",
    "        for j in range(len(chargeTimes)):\n",
    "            sl.add(chargeTimes[j])\n",
    "            s += runningCosts[j]\n",
    "            while sl and sl[-1]+(j-i+1)*s>budget:\n",
    "                sl.remove(chargeTimes[i])\n",
    "                s -= runningCosts[i]\n",
    "                i += 1\n",
    "            res = max(res, j-i+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        sum_val = 0\n",
    "        q = deque()\n",
    "        while right < len(chargeTimes):\n",
    "            while q and chargeTimes[right] >= chargeTimes[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(right)\n",
    "            sum_val += runningCosts[right]\n",
    "\n",
    "            while q and (right - left + 1) * sum_val + chargeTimes[q[0]] > budget:\n",
    "                if q[0] == left:\n",
    "                    q.popleft()\n",
    "                sum_val -= runningCosts[left]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        #今天的leetcode就做到这里了，昨天的好像还没做（悲）\n",
    "        #monotone queue\n",
    "        q=deque()\n",
    "        left=s=ans=0\n",
    "        #有left和right了，显性的窗口了\n",
    "        for right,(c,r) in enumerate(zip(chargeTimes,runningCosts)):\n",
    "            #可以看看zip，zip把可迭代对象打包成一对一对的整体\n",
    "            #入队列\n",
    "            while q and chargeTimes[q[-1]]<=c:\n",
    "                q.pop()\n",
    "            q.append(right)\n",
    "            s+=r\n",
    "            while q and chargeTimes[q[0]]+(right-left+1)*s>budget:\n",
    "                if left==q[0]:\n",
    "                    q.popleft()\n",
    "                s-=runningCosts[left]\n",
    "                left+=1\n",
    "            ans=max(ans,right-left+1)\n",
    "        return ans\n",
    "        #非常优秀的O(n)时间复杂度算法\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param chargeTimes:\n",
    "        :param runningCosts:\n",
    "        :param budget:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        l, r = 0, len(chargeTimes)\n",
    "\n",
    "        def check_ok(n):\n",
    "            sd1 = SortedList()\n",
    "            s1 = 0\n",
    "            for i in range(n):\n",
    "                s1 += runningCosts[i]\n",
    "                sd1.add((chargeTimes[i]))\n",
    "            if sd1[-1] + n * s1 <= budget:\n",
    "                return True\n",
    "            for i in range(n, len(chargeTimes)):\n",
    "                s1 += runningCosts[i]\n",
    "                sd1.add((chargeTimes[i]))\n",
    "                s1 -= runningCosts[i-n]\n",
    "                sd1.remove(chargeTimes[i - n])\n",
    "                if sd1[-1] + n * s1 <= budget:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        while l < r:\n",
    "            if l + 1 == r:\n",
    "                if check_ok(r):\n",
    "                    return r\n",
    "                return l\n",
    "            mid = (l + r) >> 1\n",
    "            if check_ok(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        Q, s = deque(), 0\n",
    "        res, i = 0, 0\n",
    "        for j,(t,c) in enumerate(zip(chargeTimes, runningCosts)):\n",
    "            while Q and Q[-1][-1]<=t:\n",
    "                Q.pop()\n",
    "            Q.append((j, t))\n",
    "            s += runningCosts[j]\n",
    "            while Q and Q[0][-1]+(j-i+1)*s>budget:\n",
    "                if Q[0][0]==i:\n",
    "                    Q.popleft()\n",
    "                s -= runningCosts[i]\n",
    "                i += 1\n",
    "            res = max(res, j-i+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        n = len(chargeTimes)\n",
    "        cost = ans = res = 0\n",
    "        q, cost_list = deque(), deque()\n",
    "        for i,x in enumerate(chargeTimes):\n",
    "            # 入栈\n",
    "            while q and x >= chargeTimes[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "            res += 1\n",
    "            cost_list.append(i)\n",
    "            cost += runningCosts[i]\n",
    "            # 出栈\n",
    "            while q and chargeTimes[q[0]] + res * cost > budget:\n",
    "                j = q[0]\n",
    "                k = cost_list[0]\n",
    "                for z in range(k, j+1):\n",
    "                    res -= 1\n",
    "                    cost -= runningCosts[cost_list.popleft()]\n",
    "                    if chargeTimes[q[0]] + res * cost <= budget: break\n",
    "                if z == j: q.popleft()\n",
    "            # print(res, q)\n",
    "            ans = max(ans, res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        n = len(chargeTimes)\n",
    "        def check(k):\n",
    "            s = 0\n",
    "            q = deque()\n",
    "            l = 0\n",
    "            for r, (x, y) in enumerate(zip(chargeTimes, runningCosts)):\n",
    "                s += y\n",
    "                while q and chargeTimes[q[-1]] < x:\n",
    "                    q.pop()\n",
    "                q.append(r)\n",
    "                while q and r - q[0] + 1 > k:\n",
    "                    q.popleft()\n",
    "                if r - l + 1 == k:\n",
    "                    if chargeTimes[q[0]] + s * k <= budget:\n",
    "                        return True\n",
    "                    s -= runningCosts[l]\n",
    "                    l += 1\n",
    "            return False\n",
    "                \n",
    "        l, r = 1, int(1e9 + 10)\n",
    "        while l <= r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        n = len(chargeTimes)\n",
    "        def check(k):\n",
    "            s = 0\n",
    "            q = deque()\n",
    "            l = 0\n",
    "            for r, (x, y) in enumerate(zip(chargeTimes, runningCosts)):\n",
    "                s += y\n",
    "                while q and chargeTimes[q[-1]] < x:\n",
    "                    q.pop()\n",
    "                q.append(r)\n",
    "                while q and r - q[0] + 1 > k:\n",
    "                    q.popleft()\n",
    "                if r - l + 1 == k:\n",
    "                    if chargeTimes[q[0]] + s * k <= budget:\n",
    "                        return True\n",
    "                    s -= runningCosts[l]\n",
    "                    l += 1\n",
    "            return False\n",
    "                \n",
    "        l, r = 1, n\n",
    "        while l <= r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        q=deque()\n",
    "        n=len(chargeTimes)\n",
    "        s=[0]*(n+1)\n",
    "        for i in range(1,n+1,1):\n",
    "            s[i]=s[i-1]+runningCosts[i-1]\n",
    "        n=len(chargeTimes)\n",
    "        # 入队\n",
    "        ans=0\n",
    "        j=0\n",
    "        for i,(c,r) in enumerate(zip(chargeTimes,runningCosts)):\n",
    "            # 入\n",
    "            while q and c>=chargeTimes[q[-1]]:\n",
    "                q.pop()\n",
    "            #\n",
    "            q.append(i)\n",
    "            while q and chargeTimes[q[0]]+(i-j+1)*(s[i+1]-s[j])>budget:\n",
    "                if q[0]==j:\n",
    "                    q.popleft()\n",
    "                j=j+1\n",
    "            ans=max(ans,i-j+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        n = len(chargeTimes)\n",
    "        s = [0] + list(accumulate(runningCosts))\n",
    "        def check(m):\n",
    "            if m == 0:\n",
    "                return True\n",
    "            # m个连续的机器人，最大开销能否满足budget\n",
    "            q = deque()\n",
    "            for i in range(n):\n",
    "                while q and chargeTimes[q[-1]] <= chargeTimes[i]:\n",
    "                    q.pop()\n",
    "                q.append(i)\n",
    "                if q and i - q[0] + 1 > m:\n",
    "                    q.popleft()\n",
    "                if q and i >= m - 1:\n",
    "                    # 1 2 3 4 5\n",
    "                    cost = chargeTimes[q[0]] + m*(s[i + 1] - s[i - m + 1])\n",
    "                    if cost <= budget:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        l,r = -1,n + 1\n",
    "        while l + 1 < r:\n",
    "            m = (l + r) >> 1\n",
    "            if check(m): # 如果可以最多运行m个，那尝试更多个\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect\r\n",
    "from collections import deque\r\n",
    "pre_sum = [0] * 50001\r\n",
    "class Solution:\r\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\r\n",
    "        n = len(chargeTimes)\r\n",
    "        for i in range(n): pre_sum[i + 1] = pre_sum[i] + runningCosts[i]\r\n",
    "\r\n",
    "        def check(ln: int) -> bool:\r\n",
    "            q: deque[int] = deque()\r\n",
    "            for i in range(ln - 1):\r\n",
    "                while q and chargeTimes[q[-1]] <= chargeTimes[i]:\r\n",
    "                    q.pop()\r\n",
    "                q.append(i)\r\n",
    "            for i in range(ln - 1, n):\r\n",
    "                while q and q[0] + ln <= i:\r\n",
    "                    q.popleft()\r\n",
    "                while q and chargeTimes[q[-1]] <= chargeTimes[i]:\r\n",
    "                    q.pop()\r\n",
    "                q.append(i)\r\n",
    "                if chargeTimes[q[0]] + ln * (pre_sum[i + 1] - pre_sum[i - ln + 1]) <= budget:\r\n",
    "                    return False\r\n",
    "            return True\r\n",
    "        \r\n",
    "        return bisect(range(1, n + 1), False, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "\n",
    "        def check(k):\n",
    "            stack = deque()\n",
    "            add = 0\n",
    "            for i in range(n):\n",
    "                # 按照值的大小右端出队\n",
    "                while stack and stack[-1][1] <= chargeTimes[i]:\n",
    "                    stack.pop()\n",
    "                stack.append([i, chargeTimes[i]])\n",
    "                # 按照索引的范围左端出队\n",
    "                while stack and stack[0][0] <= i - k:\n",
    "                    stack.popleft()\n",
    "                add += runningCosts[i]\n",
    "                if i >= k:\n",
    "                    add -= runningCosts[i - k]\n",
    "                if i >= k - 1 and stack[0][1] + k * add <= budget:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        n = len(chargeTimes)\n",
    "        low = 0\n",
    "        high = n\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        pre_sum = list(accumulate(runningCosts, initial=0))\n",
    "        q = deque()\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        for right, num in enumerate(chargeTimes):\n",
    "            while q and num > chargeTimes[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(right)\n",
    "            while q and (right-left+1)*(pre_sum[right+1]-pre_sum[left]) + chargeTimes[q[0]] > budget:\n",
    "                if q[0] == left:\n",
    "                    q.popleft()\n",
    "                left+=1\n",
    "            ans = max(ans, right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        ans = 0\n",
    "        q, deq = deque(), deque()\n",
    "        n = len(chargeTimes)\n",
    "        sm = list(accumulate(runningCosts, initial = 0))\n",
    "        for i, (x, y) in enumerate(zip(chargeTimes, runningCosts)):\n",
    "            while deq and x >= chargeTimes[deq[-1]]:\n",
    "                idx = deq.pop()\n",
    "                if deq and idx == deq[0]:\n",
    "                    deq.popleft()\n",
    "            q.append(i)\n",
    "            deq.append(i)\n",
    "            while q and chargeTimes[deq[0]] + (q[-1] - q[0] + 1) * (sm[q[-1] + 1] - sm[q[0]]) > budget:\n",
    "                v = q.popleft()\n",
    "                if deq and v == deq[0]:\n",
    "                    deq.popleft()\n",
    "            # print(q[0], q[-1], deq[0] + (q[-1] - q[0] + 1) * (sm[q[-1] + 1] - sm[q[0]]))\n",
    "            if q:\n",
    "                ans = max(ans, q[-1] - q[0] + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maximumRobots(self, chargeTimes, runningCosts, budget):\n",
    "\t\tn = len(chargeTimes)\n",
    "\t\tcq = []\n",
    "\t\ttot = 0\n",
    "\t\tl = 0\n",
    "\t\tdelay = {}\n",
    "\t\tans = 0\n",
    "\t\tfor r in range(n):\n",
    "\t\t\theapq.heappush(cq, -chargeTimes[r])\n",
    "\t\t\ttot += runningCosts[r]\n",
    "\t\t\twhile l <= r and tot * (r - l + 1) - cq[0] > budget:\n",
    "\t\t\t\tdelay[chargeTimes[l]] = delay.get(chargeTimes[l], 0) + 1\n",
    "\t\t\t\twhile cq and delay.get(-cq[0], 0) != 0:\n",
    "\t\t\t\t\tdelay[-heapq.heappop(cq)] -= 1\n",
    "\t\t\t\ttot -= runningCosts[l]\n",
    "\t\t\t\tl += 1\n",
    "\t\t\tans = max(ans, r - l + 1)\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:\n",
    "        ans=0\n",
    "        q=deque()\n",
    "        n=len(chargeTimes)\n",
    "        s=list(accumulate(runningCosts,initial=0))\n",
    "        print(s)\n",
    "        left=0\n",
    "        for i in range(n):\n",
    "            while q and chargeTimes[i]>chargeTimes[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "            while q and (i-left+1)*(s[i+1]-s[left])+chargeTimes[q[0]]>budget:\n",
    "                if q[0]==left:\n",
    "                    q.popleft()\n",
    "                left += 1\n",
    "            if q:\n",
    "                ans=max(ans,i-left+1)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
